#include <bits/stdc++.h>
using namespace std;

/*
1948. 删除系统中的重复文件夹
已解答
困难
相关标签
premium lock icon
相关企业
提示
由于一个漏洞，文件系统中存在许多重复文件夹。给你一个二维数组 paths，其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。

例如，["one", "two", "three"] 表示路径 "/one/two/three" 。
如果两个文件夹（不需要在同一层级）包含 非空且相同的 子文件夹 集合 并具有相同的子文件夹结构，则认为这两个文件夹是相同文件夹。相同文件夹的根层级 不 需要相同。如果存在两个（或两个以上）相同 文件夹，则需要将这些文件夹和所有它们的子文件夹 标记 为待删除。

例如，下面文件结构中的文件夹 "/a" 和 "/b" 相同。它们（以及它们的子文件夹）应该被 全部 标记为待删除：
/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z
然而，如果文件结构中还包含路径 "/b/w" ，那么文件夹 "/a" 和 "/b" 就不相同。注意，即便添加了新的文件夹 "/b/w" ，仍然认为 "/a/x" 和 "/b/x" 相同。
一旦所有的相同文件夹和它们的子文件夹都被标记为待删除，文件系统将会 删除 所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后，不会删除新出现的相同文件夹。

返回二维数组 ans ，该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 任意顺序 返回。

 

示例 1：


输入：paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
输出：[["d"],["d","a"]]
解释：文件结构如上所示。
文件夹 "/a" 和 "/c"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "b" 的空文件夹。
示例 2：


输入：paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
输出：[["c"],["c","b"],["a"],["a","b"]]
解释：文件结构如上所示。
文件夹 "/a/b/x" 和 "/w"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
注意，文件夹 "/a" 和 "/c" 在删除后变为相同文件夹，但这两个文件夹不会被删除，因为删除只会进行一次，且它们没有在删除前被标记。
示例 3：


输入：paths = [["a","b"],["c","d"],["c"],["a"]]
输出：[["c"],["c","d"],["a"],["a","b"]]
解释：文件系统中所有文件夹互不相同。
注意，返回的数组可以按不同顺序返回文件夹路径，因为题目对顺序没有要求。
示例 4：


输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
输出：[]
解释：文件结构如上所示。
文件夹 "/a/x" 和 "/b/x"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含名为 "y" 的空文件夹。
文件夹 "/a" 和 "/b"（以及它们的子文件夹）都会被标记为待删除，因为它们都包含一个名为 "z" 的空文件夹以及上面提到的文件夹 "x" 。
示例 5：


输入：paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
输出：[["b"],["b","w"],["b","z"],["a"],["a","z"]]
解释：本例与上例的结构基本相同，除了新增 "/b/w" 文件夹。
文件夹 "/a/x" 和 "/b/x" 仍然会被标记，但 "/a" 和 "/b" 不再被标记，因为 "/b" 中有名为 "w" 的空文件夹而 "/a" 没有。
注意，"/a/z" 和 "/b/z" 不会被标记，因为相同子文件夹的集合必须是非空集合，但这两个文件夹都是空的。
 

提示：

1 <= paths.length <= 2 * 104
1 <= paths[i].length <= 500
1 <= paths[i][j].length <= 10
1 <= sum(paths[i][j].length) <= 2 * 105
path[i][j] 由小写英文字母组成
不会存在两个路径都指向同一个文件夹的情况
对于不在根层级的任意文件夹，其父文件夹也会包含在输入中
*/

// 法一
class Solution {
public:
    // 文件夹结构体
    struct Node {
        unordered_map<string, Node*> children;      // 映射结构 name -- node
        string hash;                                // 节点结构哈希 反映文件夹结构
        bool toDel = false;                         // 是否删除的标志量
        ~Node () {
            for (auto& [name, child] : children) {
                delete child;
            }
        }
    };

    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        // 构建文件夹结构
        Node* root = new Node();
        // 遍历文件夹路径
        for (auto& path : paths) {
            Node* cur = root;
            // 寻找子文件夹
            for (auto& folder : path) {
                // 子文件夹不存在就创建处理
                if (cur->children.find(folder) == cur->children.end())
                    cur->children[folder] = new Node();

                // cd folder
                cur = cur->children[folder];
            }
        }
        
        // 后续遍历生成树(此处就是生成每个节点的结构哈希)
        function<string(Node*)> generateHash = [&](Node* node) {
            // null 处理
            if (node->children.empty()) {
                // 叶子节点 没有孩子  那么就是 ""
                // node->children = "";
                return /*node->children*/std::string("");
            }

            // 向量容器 存储 多个孩子节点
            vector<string> childParts;
            for (auto& [name, child] : node->children)  
                childParts.push_back(name + ":" + generateHash(child) + ";");

            // sort 来保证结构相同 那么哈希就相同
            sort(childParts.begin(), childParts.end());
            // 拼接 节点信息 -->节点哈希
            string hashStr;
            for (auto& part : childParts)  
                hashStr += part;
            
            node->hash = hashStr;
            return std::string(node->hash);
        };
        
        // 从根节点开始生成哈希
        generateHash(root);

        // 从生成的哈希中获取信息 统计哈希出现次数 一个哈希出现一次就是一次重复 (必须非空)
        unordered_map<string, int> hashCount;
        function<void(Node*)> countHashes = [&](Node* node) {
            // 非空  计数器++
            if (!node->hash.empty())    
                hashCount[node->hash]++;
            // 递归 统计全部
            for (auto& [name, child] : node->children)  
                countHashes(child);
        };
        countHashes(root); 

        // 统计出来的 发现重复就标记(需要删除 然后迭代一起删除)
        function<void(Node*)> markDelHashs = [&](Node* node) {
            // 哈希冲突数量 > 1 标志量变成true  代表需要删除
            if (!node->hash.empty() && hashCount[node->hash] > 1)   
                node->toDel = true;

            // 递归删除 
            for (auto& [name, child] : node->children) {
                markDelHashs(child);
                // 有冲突的文件夹 是将其路径下所有子文件夹都删完
                if (node->toDel)        
                    child->toDel = true;
            }
        };
        markDelHashs(root);     

        // 存储 包含删除所有标记文件夹之后剩余文件夹的路径
        vector<vector<string>> ans;
        for (auto& path : paths) {
            Node* cur = root;
            bool flag = true;
            for (auto& folder : path) {
                cur = cur->children[folder];
                // 有待删除的节点那么该路径就被排除
                if (cur->toDel) {
                    flag = false;
                    break;
                }
            }
            // 状态量前提下 路径进容器
            if (flag)   
                ans.push_back(path);
        }
        
        delete root;
        return ans;
    }
};

// 法二
using ULL = uint64_t;  // 无符号长整型用于哈希值
const ULL BASE = 97755331;  // 哈希基数
const ULL MASK = 23367;    // 哈希掩码
const int MAX_PATHS = 20001;  // 最大路径数量

// 前置声明：告诉编译器 FolderNode 是一个类
class FolderNode;

// 全局标记数组：标记需要删除的路径索引
int shouldDelete[MAX_PATHS] = {0};
// 全局哈希表：存储结构哈希到对应节点的映射
unordered_map<ULL, vector<FolderNode*>> hashMap;

// 字符串哈希函数  字符串转哈希值
ULL hashString(string& str) {
    ULL ans = 0;
    for (char c : str)  ans = ans * BASE + c;
    return ans;
}

// 文件系统中的一个文件夹 
class FolderNode {
public:  // 改为public，允许外部访问成员和方法
    unordered_map<ULL, FolderNode*> children;    // 子文件夹哈希 -> 子节点（修正：添加逗号）
    ULL nodeHash;                               // 当前节点结构哈希
    ULL pathHash;                               // 路径字符串的哈希
    int pathIdx;                                // 原始路径对应索引     -1 非叶子节点

    // 构造函数（修正：分号改为花括号）
    FolderNode() : nodeHash(0), pathIdx(-1) {}

    // 递归添加路径 进哈希结构树
    void addPath(vector<string>::iterator cur, vector<string>::iterator end, int pathIdx, ULL parentHash) {
        if (cur == end) {
            // 路径末尾记录索引和路径哈希
            this->pathIdx = pathIdx;
            pathHash = parentHash * (parentHash ^ MASK);    // 掩码做哈希处理
            return;
        }

        // 记录 cur 的名称哈希
        ULL nameHash = hashString(*cur);
        // 不存在建新的子字符串 子路径（修正：find()添加参数nameHash）
        if (children.find(nameHash) == children.end())  children[nameHash] = new FolderNode();

        // 递归添加 
        children[nameHash]->addPath(cur + 1, end, pathIdx, parentHash);
    }

    // 递归上传哈希  然后筛选出重复的结构
    void uploadHash() {
        // 遍历处理
        for (auto& [nameHash, child] : children) {
            child->uploadHash();
            // 计算当前 的 结构哈希 --> 基于子节点的哈希组合
            nodeHash += child->nodeHash * BASE + (child->pathHash ^ child->nodeHash); 
        }

        // 叶子节点或者没有子文件夹(0) 不处理
        if (pathIdx == -1 || nodeHash == 0)     return;

        // 当前节点进哈希map 检测重复结构（修正：笔误修正）
        hashMap[nodeHash].push_back(this);
        auto& dup = hashMap[nodeHash];

        // 有第二个重复节点 那么代表重复 标记为需要删除
        if (dup.size() == 2) {
            markFunc(dup[0]);
            markFunc(dup[1]);
        } else if (dup.size() > 2)  markFunc(dup.back());   // 有更多重复 标记当前 下一轮递归也会删除的
    }

    // 单例标记方法 
    static void markFunc(FolderNode* node) {
        for (auto& [nameHash, child] : node->children)  markFunc(child);
        // 相关索引 > 0 需要删除的索引重新从最开始回来开始新一轮递归
        if (node->pathIdx >= 0)     shouldDelete[node->pathIdx] = 1;
    }
};

class Solution {
public:
    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& paths) {
        // 初始化标记
        memset(shouldDelete, 0, sizeof(shouldDelete));
        hashMap.clear();
        // 文件夹的路径层级越深 路径更长  优化就是先处理短的（修正：returnn拼写错误）
        sort(paths.begin(), paths.end(), [](auto& a, auto& b) {
            return a.size() < b.size();    
        });

        // 文件夹树
        FolderNode root;
        int pathCount = paths.size();
        for (int i = 0; i < pathCount; ++i) {
            // 计算路径最后一个文件夹的哈希作为父哈希
            ULL parentHash = hashString(paths[i].back());
            root.addPath(paths[i].begin(), paths[i].end(), i, parentHash);
        }
        
        // 上传哈希值并标记重复文件夹
        root.uploadHash();
        
        // 收集未被标记删除的路径
        vector<vector<string>> result;
        for (int i = 0; i < pathCount; ++i) {
            if (!shouldDelete[i]) {
                result.push_back(move(paths[i]));
            }
        }
        
        return result;
    }
};